//
// Created by guo on 2025/3/18.
//

#ifndef BBDEMO_LOCKFREE_QUEUE_H
#define BBDEMO_LOCKFREE_QUEUE_H
#include <atomic>
#include <memory>

/**
 * 无锁队列模板类
 * @tparam T 队列元素类型
 * @说明 基于链表实现，使用原子操作保证线程安全，适合多生产者多消费者场景
 * @注意 内存回收机制未实现生产级安全，建议结合Hazard Pointers使用
 */
template <typename T>
class LockFreeQueue {
private:
    // 队列节点结构
    struct Node {
        T data;                      // 节点数据
        std::atomic<Node*> next;     // 原子指针指向下一节点

        // 构造节点（支持拷贝和移动语义）
        Node(const T& data) : data(data), next(nullptr) {}
        Node(T&& data) : data(std::move(data)), next(nullptr) {}
    };

    // 原子指针维护队列头尾
    std::atomic<Node*> head;  // 头指针（总指向虚拟头节点）
    std::atomic<Node*> tail;  // 尾指针

public:
    /**
     * 构造函数：初始化虚拟头节点
     * @说明 虚拟头节点消除队列空状态的特殊处理，
     *       使得入队出队操作可以共享相同逻辑
     */
    LockFreeQueue() {
        Node* dummy = new Node(T());  // 创建虚拟节点
        head.store(dummy, std::memory_order_relaxed);
        tail.store(dummy, std::memory_order_relaxed);
    }

    /**
     * 析构函数：释放所有节点内存
     * @警告 非线程安全，假设析构时无其他线程访问队列
     */
    ~LockFreeQueue() {
        while (Node* old_head = head.load(std::memory_order_relaxed)) {
            head.store(old_head->next.load(std::memory_order_relaxed),
                       std::memory_order_relaxed);
            delete old_head;
        }
    }

    /**
     * 检查队列是否为空
     * @警告 该函数返回瞬时状态，可能被其他线程立即修改
     * @return true 如果队列可能为空（存在假阴性）
     * @说明 由于无锁特性，empty()的结果不可靠，建议优先检查dequeue()的返回值
     */
    bool empty() const noexcept {
        Node* current_head = head.load(std::memory_order_acquire);
        Node* current_tail = tail.load(std::memory_order_acquire);
        Node* next_node = current_head->next.load(std::memory_order_acquire);

        // 队列为空的充分条件：
        // 1. 头尾指针指向同一节点（可能是虚拟头节点）
        // 2. 头节点的next指针为空
        return (current_head == current_tail) && (next_node == nullptr);
    }

    /**
     * 入队操作：将元素添加到队列尾部
     * @param data 要入队的元素
     * @算法 采用"帮助式"入队策略：
     *       1. 创建新节点
     *       2. 循环尝试将节点链接到当前尾部
     *       3. 辅助完成其他线程未完成的尾节点更新
     */
    void enqueue(const T& data) {
        Node* new_node = new Node(data);
        Node* current_tail = nullptr;
        Node* tail_next = nullptr;

        while (true) {
            // 获取当前尾节点及其下一个节点的快照
            current_tail = tail.load(std::memory_order_acquire); // 获取最新尾节点
            tail_next = current_tail->next.load(std::memory_order_acquire);

            // 检查尾节点是否已被其他线程修改
            if (current_tail != tail.load(std::memory_order_relaxed)) {
                continue;  // 若已变化则重试
            }

            if (tail_next != nullptr) {
                // 情景：尾节点已落后，帮助其他线程推进尾指针
                tail.compare_exchange_weak(
                        current_tail, tail_next,
                        std::memory_order_release,  // 成功时同步到其他线程
                        std::memory_order_relaxed
                );
            } else {
                // 尝试将新节点链接到链表尾部
                if (current_tail->next.compare_exchange_weak(
                        tail_next, new_node,
                        std::memory_order_release,  // 成功时新节点对其他线程可见
                        std::memory_order_relaxed
                )) {
                    break;  // 链接成功，退出循环
                }
            }
        }

        // 尝试将尾指针移动到新节点（可能失败，但最终会被其他线程完成）
        tail.compare_exchange_strong(
                current_tail, new_node,
                std::memory_order_release,
                std::memory_order_relaxed
        );
    }

    /**
     * 出队操作：尝试从队列头部取出元素
     * @param result 存储取出元素的引用
     * @return bool 是否成功取出元素
     * @算法 采用"双重检查"策略：
     *       1. 检测队列是否为空
     *       2. 协助推进可能的滞后尾指针
     *       3. 原子性地移动头指针
     */
    bool dequeue(T& result) {
        Node* current_head = nullptr;
        Node* current_tail = nullptr;
        Node* next_node = nullptr;

        while (true) {
            current_head = head.load(std::memory_order_acquire);
            current_tail = tail.load(std::memory_order_acquire);
            next_node = current_head->next.load(std::memory_order_acquire);

            // 验证头指针是否已被其他线程修改
            if (current_head != head.load(std::memory_order_relaxed)) {
                continue;  // 已变化则重试
            }

            if (current_head == current_tail) {
                if (next_node == nullptr) {
                    return false;  // 队列真正为空
                }
                // 尾指针落后，帮助推进到尾节点的下一个
                tail.compare_exchange_weak(
                        current_tail, next_node,
                        std::memory_order_release,
                        std::memory_order_relaxed
                );
            } else {
                // 预加载数据以避免在CAS成功后访问已释放内存
                result = std::move(next_node->data);

                // 尝试原子性地移动头指针
                if (head.compare_exchange_weak(
                        current_head, next_node,
                        std::memory_order_release,
                        std::memory_order_relaxed
                )) {
                    delete current_head;  // 安全删除旧头节点
                    return true;
                }
            }
        }
    }

    // 禁用拷贝构造和赋值操作
    LockFreeQueue(const LockFreeQueue&) = delete;
    LockFreeQueue& operator=(const LockFreeQueue&) = delete;
};

#endif //BBDEMO_LOCKFREE_QUEUE_H
